#(入门)一对兔子，从出生后第3个月起每个月都生一对兔子，
# 小兔子长到第三个月后每个月又生一对兔子，
# 假如兔子都不死，每个月的兔子总数是多少？（输出前10个月即可）
# def inc(n):
#     if n==1 or n==2:
#         return 1
#     prev1,prev2=1,1
#     for month in range(3,n+1):
#         current=prev1+prev2
#         prev2=prev1
#         prev1=current
#     return prev1
#
# for month in range(1,11):
#     print(f"第{month}个月兔子的总数为：{inc(month)*2}")




# (进阶)在N×N的棋盘上摆放N个皇后，使其不能互相攻击，即任意的两个皇后不能处在同一行，同一列，或同一斜线上。请输出对于N有多少种摆放。
# 输入例子：4
# 输出例子：Total count: 2
def queens(n):
    def is_safe(board,row,col):
        #检查列上是否有皇后
        for i in range(row):
            if board[i]==col:
                return False

        # 检查左上对角线是否有皇后
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i] == j:
                return False

        # 检查右上对角线是否有皇后
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
            if board[i] == j:
                return False

        return True

    def solve(board, row):
        # 如果所有行都成功放置了皇后，则找到一个解
        if row == n:
            return 1

        count = 0
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col  # 放置皇后
                count += solve(board, row + 1)  # 递归放置下一行的皇后
                board[row] = -1  # 回溯，撤销选择

        return count

    # 初始化棋盘，-1表示该位置没有皇后
    board = [-1] * n
    return solve(board, 0)


# 输入例子
n = 4
# 输出例子
print(f"Total count: {queens(n)}")
